
function AlgoUtils() {

    /*
    ** 从 martrix矩阵中找到start到end的最短路径
    ** @param matrix: 矩阵，用一维数组保存
    ** @param start: 其实点
    ** @param end: 终止点
    ** @param validIdxArr: 限定数组：输出的路径中的索引，只能出现在这个数组中
    ** @return 路径数组，0:起始点, 最后一个元素:终点
    ** 
    */
    this.findShortestPath = function(hang, lie, startIdx, endIdx, validIdxArr) {
        const rows = hang;
        const cols = lie;
        const start = {row: Math.floor(startIdx / lie), col: startIdx % lie};
        const end = {row: Math.floor(endIdx / lie), col: endIdx % lie};
      
        const directions = [
          { row: -1, col: 0 }, // 上
          { row: 1, col: 0 },  // 下
          { row: 0, col: -1 }, // 左
          { row: 0, col: 1 }   // 右
        ];
      
        const queue = [];
        const visited = Array.from({ length: rows }, () => Array(cols).fill(false));
        const distances = Array.from({ length: rows }, () => Array(cols).fill(Infinity));
        const parents = Array.from({ length: rows }, () => Array(cols));
      
        const isValidPoint = (row, col) => {
          const pointIndex = row * cols + col;
          return validIdxArr.includes(pointIndex);
        };
      
        queue.push(start);
        visited[start.row][start.col] = true;
        distances[start.row][start.col] = 0;
      
        while (queue.length > 0) {
          const current = queue.shift();
      
          if (current.row === end.row && current.col === end.col) {
            break;
          }
      
          for (const direction of directions) {
            const newRow = current.row + direction.row;
            const newCol = current.col + direction.col;
      
            if (
              newRow >= 0 &&
              newRow < rows &&
              newCol >= 0 &&
              newCol < cols &&
              !visited[newRow][newCol] &&
              isValidPoint(newRow, newCol)
            ) {
              queue.push({ row: newRow, col: newCol });
              visited[newRow][newCol] = true;
              distances[newRow][newCol] = distances[current.row][current.col] + 1;
              parents[newRow][newCol] = current;
            }
          }
        }
      
        const shortestPath = [];
        let current = end;
        while (current) {
          shortestPath.unshift(current.row * lie + current.col);
          current = parents[current.row][current.col];
        }

        return shortestPath;
    }
}

var gAlgoUtils = new AlgoUtils();
// const shortestPath = gAlgoUtils.findShortestPath(5, 5, 0, 24, [0, 1, 6, 7, 12, 13, 18, 19, 20, 21, 22, 23, 24]);
// console.log("shortestPath=" + shortestPath);